package dp;

/**
 * leet-code(55) 跳跃游戏
 *
 * @author Ringo
 * @date 2021/8/29 22:11
 */
public class CanJump {

    public static void main(String[] args) {
        int[] nums1 = {2, 3, 1, 1, 4};
        int[] nums2 = {3, 2, 1, 0, 4};
        System.out.println(canJumpInDP(nums1));
        System.out.println(canJumpInDP(nums2));
        System.out.println(canJump(nums1));
        System.out.println(canJump(nums2));
    }

    public static boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0)
            return true;
        int n = nums.length;

        // 能跳最远的下标
        int furthest = 0;

        for (int i = 0; i < n; ++i) {
            if (i > furthest) return false;
            furthest = Math.max(nums[i] + i, furthest);
        }

        return true;
    }


    // 1: 动态规划
    public static boolean canJumpInDP(int[] nums) {
        if (nums == null || nums.length == 0)
            return true;
        int n = nums.length;
        // dp[i] 表示能否 跳到 i
        boolean[] dp = new boolean[n];
        dp[0] = true;

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; j++) {
                // 能跳到 j && 可以从 j 跳到 i ==> 可以跳到 i
                if (dp[j] && nums[j] + j >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n - 1];
    }

}
